package com.guaoran.algorithm.binary.tree.order;

import com.guaoran.algorithm.common.CommonUtil;
import com.guaoran.algorithm.entity.TreeNode;

import java.util.*;

/**
 * @author : 孤傲然
 * @description : 二叉树层级顺序遍历
 * https://leetcode.com/problems/binary-tree-level-order-traversal/
 * @date :2021/1/23 23:30
 */
public class LevelOrderTraversal {
    public static void main(String[] args) {
        TreeNode treeNode = CommonUtil.createTreeNode(new Integer[]{3,9,20,null,null,15,7});
        System.out.println(CommonUtil.readTreeNode(treeNode));
        System.out.println(levelOrder(CommonUtil.createTreeNode(new Integer[]{1,2})));
    }

    public static List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if(root == null){
            return result;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        result.add(Collections.singletonList(root.val));
        while(!queue.isEmpty()){
            int size = queue.size();
            List<Integer> list = new ArrayList<>();
            for(int i = 0; i < size; i++){
                TreeNode treeNode = queue.poll();
                if(treeNode.left == null && treeNode.right == null){
                    continue;
                }
                if(treeNode.left != null){
                    list.add(treeNode.left.val);
                    queue.offer(treeNode.left);

                }
                if(treeNode.right != null){
                    list.add(treeNode.right.val);
                    queue.offer(treeNode.right);
                }
            }
            if(!list.isEmpty()){
                result.add(list);
            }
        }
        return result;

    }
}
